package 力扣日常刷题.木22一月.第08天0116;

/**
 * @author 帅小伙
 * @date 2022/1/16
 * @description
 * 字节面试题
 */
public class Demo05动态规划最大正方形 {




    public int maximalSquare(char[][] matrix) {
        int maxEdge = 0;
        int n = matrix.length;
        int m = matrix[0].length;

        int[][] dp = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(matrix[i][j] == '1'){
                    if(i==0 || j == 0) dp[i][j] = 1;
                    else {
                        dp[i][j] = Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
                    }
                }
                maxEdge = Math.max(maxEdge,dp[i][j]);
            }
        }
        return maxEdge*maxEdge;
    }

}
